package one.linkList;

/**
 * K 个一组翻转链表
 * 时间复杂度：O(n)
 * 思路：
 * 1）k个一组，找到每组的最后一个节点；
 * 2）反转每小组链表；
 * 3）将小组之间连接起来
 */
public class ReverseKGroup {
    //时间复杂度：
    //思路：1）k个一组，找到每组的最后一个节点；2）反转每小组链表；3）将小组之间连接起来
    //3）分组（找到每一组的开始、结尾），按组遍历
    public static ListNode reverseKGroup(ListNode head, int k) {
        //建立一个帮助节点
        ListNode protect = new ListNode(0, head);
        //last：上一组的结尾
        ListNode last = protect;
        while(head != null){
            ListNode end = getKend(head, k);
            if(end == null){
                break;
            }

            ListNode nextGroupHead = end.next;
            //处理head到end之间的k-1条边的反转
            reverseLinkedList(head, end);
            //上一组跟本组的新开始（旧end）建立联系
            last.next = end;
            //本组的新结尾（head）和下一组建立联系
            head.next = nextGroupHead;

            //分组遍历
            last = head;
            head = nextGroupHead;
        }
        return protect.next;
    }
    //1）k个一组，找到每组的最后一个节点；(step=k-1：走k-1步，就可以找到每一组的最后一个节点了)
    private static ListNode getKend(ListNode head, int k){
        while(head != null){
            k--;
            if(k == 0) break;
            head = head.next;
        }
        return head;
    }
    //2）反转每小组链表；（使用无帮助节点的方法）
    private static void reverseLinkedList(ListNode head, ListNode end){
        if(head == end) return;
        ListNode pre = head;
        head = head.next;
        //改每条边，所以需要访问链表
        while(head != end){
            ListNode nextHead = head.next;
            //改一条边
            head.next = pre;
            //last,head向后移动一位
            pre = head;
            head = nextHead;
        }
        end.next = pre;
    }

    public static void main(String[] args) {
        ListNode l = new ListNode(1, new ListNode(2, new ListNode(3
                , new ListNode(4, new ListNode(5, new ListNode(6))))));
        reverseKGroup(l, 2);
        while (l != null){
            System.out.print(l.val + " ==> ");
            l = l.next;
        }
    }
}

